#include <bits/stdc++.h>
using namespace std;

/*
368. 最大整除子集
已解答
中等
相关标签
相关企业
给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
answer[i] % answer[j] == 0 ，或
answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。

 

示例 1：

输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。
示例 2：

输入：nums = [1,2,4,8]
输出：[1,2,4,8]
 

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 109
nums 中的所有整数 互不相同
*/

// 法一
class Solution {
public:
	vector<int> largestDivisibleSubset(vector<int>& nums) {
		// dp
		if(nums.empty())      return {};
		sort(nums.begin(), nums.end()); // 递增

		int n = nums.size();
		vector<int> dp(n, 1);   // dp[i]表示以nums[i]为结尾的最大整除子集的大小
		vector<int> prev(n, -1); // prev[i]记录nums[i]的前一个数的索引
		int maxSize = 1, maxIndex = 0;
		// 计算两个数组
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if(nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1;
					prev[i] = j;
				}
			}
			// 更新
			if (dp[i] > maxSize) {
				maxSize = dp[i];
				maxIndex = i;
			}
		}
		// 回溯
		vector<int> ans;
		while (maxIndex != -1) {
			ans.push_back(nums[maxIndex]);
			maxIndex = prev[maxIndex];
		}
		reverse(ans.begin(), ans.end());
		return ans;
	}
};

// 法二
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> dp(n, 1);  // dp[i] 表示以 nums[i] 结尾的最长子集长度
        int maxSize = 1, maxVal = nums[0];
        
        // 动态规划计算 dp 数组
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] % nums[j] == 0) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            if (dp[i] > maxSize) {
                maxSize = dp[i];
                maxVal = nums[i];
            }
        }
        vector<int> res;
        if (maxSize == 1) {
            res.push_back(nums[0]);
            return res;
        }    
        // 倒推重构最大子集
        for (int i = n - 1; i >= 0 && maxSize > 0; --i) {
            if (dp[i] == maxSize && maxVal % nums[i] == 0) {
                res.push_back(nums[i]);
                maxVal = nums[i];
                maxSize--;
            }
        }    
        return res;
    }
};